package sort


fun main(args: Array<String>) {


    val num = arrayOf(3, 1, 0, 10, 9, 100, 34, 5, 45)

    insertSort(num)

    println(num.toList())
}


/**
 * 插入排序： 前面 n-1 个数都是有序的，寻找 n 个数在 已有 有序数组中的位置，和冒泡排序一样的时间复杂度，最好是 O(N)
 * 空间复杂度是 O(1)
 *
 */
fun insertSort(num: Array<Int>) {


    if (num.size <= 1)
        return


    for (i in 0 until num.size) {

        val curr = num[i]


        var j = i
        while (j > 0 && num[j - 1] > curr)
            j--


        var k = i
        while (k > j) {
            num[k] = num[k - 1]
            k--

        }

        num[j] = curr


    }


//    if (num.size < 2)
//        return
//
//    for (i in 0 until num.size) {
//
//        val curr = num[i]
//
//        var j = i
//
//        //找到插入位置
//        while (j > 0 && num[j - 1] > curr)
//            j--
//
//        // j 以后的元素都要后移 从 j 到 i 之间的元素都要后移
//        for (k in i downTo j + 1)
//            num[k] = num[k - 1]
//
//        //最后插入正确的位置
//        num[j] = curr
//}
}
